package offer;

/**
 * @Author Elephas
 * @Date 2022/1/31
 **/
public interface NumberOfSteps {
    int numberOfSteps(int num);
}
class NumberOfStepsImpl1 implements NumberOfSteps{

    @Override
    public int numberOfSteps(int num) {
        int iterNum = 0;
        while(num != 0){
            if(num % 2 == 1){
                num -- ;
            }else {
                num >>= 1;
            }
            iterNum++;
        }
        return iterNum;
    }
}
class NumberOfStepsImpl2 implements NumberOfSteps{
    public static void main(String[] args) {
       int a = new NumberOfStepsImpl2().numberOfSteps(14);
       int b = new NumberOfStepsImpl2().numberOfSteps(Integer.MAX_VALUE);
       int c = new NumberOfStepsImpl2().numberOfSteps(Integer.MAX_VALUE>>1);
       System.out.println(a+"    "+b+"    "+c);

    }

    static final int BIT_16 = 0xFFFF0000;
    static final int BIT_8 = 0x0000FF00;
    static final int BIT_4 = 0x000000F0;
    static final int BIT_2 = 0x0000000C;
    static final int BIT_1 = 0x00000002;
    static final int BIT_0 = 0x00000001;
    static final int[] BITS = new int[]{BIT_16,BIT_8,BIT_4,BIT_2,BIT_1,BIT_0};
    static final int[] BITS_WEIGHT = new int[]{16,8,4,2,1,1};
    @Override
    public int numberOfSteps(int num) {
        if(num == 0){
            return 0;
        }
        int numbers = 0;
        int bitCounts = num;
        for (int i = 0; i < BITS.length; i++) {
            if((num & BITS[i]) != 0){
                numbers += BITS_WEIGHT[i];
                num >>= BITS_WEIGHT[i];
            }
        }
        
        bitCounts = (bitCounts & 0x55555555) + ((bitCounts >> 1) & 0x55555555);
        bitCounts = (bitCounts & 0x33333333) + ((bitCounts >> 2) & 0x33333333);
        bitCounts = (bitCounts & 0x0f0f0f0f) + ((bitCounts >> 4) & 0x0f0f0f0f);
        bitCounts = (bitCounts & 0x00ff00ff) + ((bitCounts >> 8) & 0x00ff00ff);
        bitCounts = (bitCounts & 0x0000ffff) + ((bitCounts >> 16) & 0x0000ffff);

        return numbers + bitCounts - 1 ;
    }
}
